package main

import (
	"fmt"
	"strings"
	"time"
)

type QueenBoard [][]string

var resule []QueenBoard

func init() {
	resule = []QueenBoard{}
}

func main() {
	n := 8
	q := initBoard(n)

	start := time.Now()
	solveNQueens(q, 0)

	fmt.Println("result", len(resule))
	fmt.Printf("speed time %d ms\n", time.Now().Sub(start).Milliseconds())
}

func solveNQueens(board QueenBoard, row int) {
	//触发满足条件
	if row == len(board) {
		resule = append(resule, board)
		return
	}
	for col := 0; col < len(board); col++ {
		if !isVaild(board, row, col) {
			continue
		}
		//做选择
		board[row][col] = "Q"
		solveNQueens(copyBoard(board), row+1)
		//撤销选择
		board[row][col] = "."
	}
}

func initBoard(n int) (q QueenBoard) {
	q = QueenBoard{}
	for i := 0; i < n; i++ {
		oneRow := []string{}
		for i := 0; i < n; i++ {
			oneRow = append(oneRow, ".")
		}
		q = append(q, oneRow)
	}
	return
}

//校验是否合法
func isVaild(board QueenBoard, row, col int) bool {
	//上方
	for y := row - 1; y >= 0; y-- {
		if board[y][col] == "Q" {
			return false
		}
	}
	//左上方
	for x, y := col-1, row-1; x >= 0 && y >= 0; x, y = x-1, y-1 {
		if board[y][x] == "Q" {
			return false
		}
	}
	//右上方
	for x, y := col+1, row-1; x <= len(board)-1 && y >= 0; x, y = x+1, y-1 {
		if board[y][x] == "Q" {
			return false
		}
	}
	return true
}

//打印棋盘
func PrintBoard(board QueenBoard) {
	fmt.Println("========================")
	if board == nil || len(board) == 0 || len(board[0]) == 0 {
		fmt.Println("异常棋盘")
		return
	}
	for row := 0; row < len(board); row++ {
		fmt.Println(strings.Join(board[row], " "))
	}
}

//复制棋盘
func copyBoard(board QueenBoard) (copyBoard QueenBoard) {
	if board == nil {
		return
	}
	copyBoard = QueenBoard{}
	for row := 0; row < len(board); row++ {
		cpRow := []string{}
		for col := 0; col < len(board); col++ {
			cpRow = append(cpRow, board[row][col])
		}
		copyBoard = append(copyBoard, cpRow)
	}
	return copyBoard
}
